Conventional high speed communications on copper media (e.g. standard telephone lines) use DMT technology and are bundled under the umbrella of xDSL. There are several variants of this technology currently deployed, namely Asymmetric Digital Subscriber Line (ADSL), ADSL2, ADSL2plus, and Very High Speed Digital Subscriber Line (VDSL). Some of these technologies are standardized by the International Telecommunications Union, Geneva, (ITU) as follows: “ITU-T Recommendation G992.1, Asymmetric Digital Subscriber Line (ADSL),” “ITU-T Recommandation G992.3, Asymmetric Digital Subscriber Line Transceivers 2 (ADSL2),” “ITU-T Recommendation G992.5, Asymmetric Digital Subscriber Line (ADSL) Transceivers—Extended Bandwidth ADSL2 (ADSL2plus),” and “ITU-T Recommendation G993.1, Very High Speed Asymmetric Digital Subscriber Line (VDSL) Transceivers.” These and other systems are the subject of ongoing and future standardization efforts.
One key feature of such xDSL modems is the use of FEC to combat the effects of impulse noise on the lines. The FEC used is typically the well known Reed Solomon code, with a maximum codeword size of 255 bytes. These coders add redundancy to data by appending R check bytes to each block of data, allowing for the correction of R/2 random errors per block, where:N=K+R,and there are K data bytes and R check bytes in each codeword block of N bytes.
In order to enhance the effectiveness of error correction, a convolutional interleaver is added to spread the error pattern over many DMT symbols, thus allowing for the correction of such errors without introducing excessive redundancy and, hence, overhead. The convolutional interleaver has the following property:Δj=(D−1)j j=1, . . . , I−1,where,                Δj is the distance between two interleaved bytes,        D is the interleaver depth, and        I is the interleaver block size.        
A necessary condition of such an interleaver is that D and I must be co-prime (i.e. have no common divisor). This has been enforced in different ways:in ADSL D=2n I=N=odd integer, andin VDSL D=M·I+1 with N=q·I,where q is an integer fraction. Finally, a generalized interleaver has also been considered where:in any DSL D=M·I+x with N=q·I x=1, . . . ,I−1,with the constraint that x is chosen such that D and I are mutually co-prime. Generally, these conditions place one constraint on the choice of D and N.
In a DMT modem, the data is broken into frames and transmitted on a set of discrete tones in each frame, also called a DMT symbol. In xDSL, the frame or symbol rate is typically 4 kHz. The number of DMT symbols per FEC codeword is a variable designated as S in the standards. Traditionally, S is an integer or an integer fraction, but more recent standards have relaxed this to allow non-integer values of S. However, the minimum value of S is limited to some specified value Smin, which effectively limits the number of times the FEC decoder is run every DMT frame and has a direct influence on complexity and cost. This leads to a second constraint on the choice of FEC parameters.
The convolutional interleaver was introduced to combat impulse noise. Due to the nature of DMT modems, any impulse noise corrupts at least one whole DMT frame of data. This leads to the definition of a parameter, INPmin, that specifies how many DMT frames (symbols) the FEC must correct. This defines a third constraint on the choice of FEC parameters.
Other possible constraints on the choice of FEC parameters include the delay introduced by the interleaver, defined as MaxLatency, and the total memory required, defined a MaxMemory.
A DMT modem is required to allocate the bits in an input stream to the tones in a DMT frame. This process is known as bit allocation, and is based on the Signal-to-Noise Ratio (SNR) per tone, using well known algorithms based on the relationship:bitsi=round((snr(tonei)−snrGap−margin+cg)/3),where snr is expressed in dB, the snrGap is approx 9.7 dB, margin is a noise margin parameter, and cg is any coding gain. All bit allocation algorithms are required to take into account any coding gain introduced by the FEC, which is a function of the FEC parameters. This leads to an iterative solution where a first set of FEC parameters is determined assuming no FEC coding gain, and the parameters are adjusted to take into account the coding gain for the chosen FEC parameters. This process is repeated until no difference is observed. Thus, the final outcome is a process for choosing both the bit allocation and the FEC parameters using a computational engine on the modem to achieve optimum performance in the presence of all of the specified constraints.
In conventional implementations, the determination of the optimal FEC parameters is by some form of search over a large set of possible values in order to satisfy all of the constraints.